// 写法一：
// 为了简单用数组表示 行列用数组的索引表示  比如cur=0表示第一列
function queen(a, cur) {  // cur表示当前列
  if (cur == a.length) {  // 数组填满了 代表一种 Q解法  打印答案
    console.log('a:', a);
    return;
  }
  // 遍历循环  当前列从第一行到第n行开始试值
  for (var i = 0; i < a.length; i++) {  // 所以此时的i表示在第cur列的第i行放置Q
    a[cur] = i;
    var flag = true;
    // 此时看当前放置的Q会不会和之前放置的Q起冲突，所以在此处遍历cur之前的列
    for (var j = 0; j < cur; j++) { // j表示前面的第几列
      var ab = i - a[j];
      // a[j] == i 表示 当前列放置的Q和之前行放置的Q处于同一行，不符合
      //  (ab>0?ab:-ab)==cur-j  表示   当前列放置的Q和之前行放置的Q处于对角线  不符合
      if (a[j] == i || (ab > 0 ? ab : -ab) == cur - j) { flag = false; break };
    };
    if (flag) { queen(a, cur + 1); }
  };
};
queen([1, 1, 1, 1], 0);

// 写法二：
let solveNQueens = function (n) {
  let res = []
  // 已摆放皇后的的列下标
  let columns = []
  // 已摆放皇后的对角线1下标 左下 -> 右上
  // 计算某个坐标是否在这个对角线的方式是「行下标 + 列下标」是否相等
  let dia1 = []
  // 已摆放皇后的对角线2下标 左上 -> 右下
  // 计算某个坐标是否在这个对角线的方式是「行下标 - 列下标」是否相等
  let dia2 = []

  // 在选择当前的格子后 记录状态
  let record = (rowIndex, columnIndex, bool) => {
    columns[columnIndex] = bool
    dia1[rowIndex + columnIndex] = bool
    dia2[rowIndex - columnIndex] = bool
  }

  // 尝试在一个n皇后问题中 摆放第index行内的皇后位置
  let putQueen = (rowIndex, prev) => {
    console.log(tag(rowIndex, '=', true) + `第${rowIndex}行【${prev}】` + tag(rowIndex, '=', false))
    if (rowIndex === n) {
      console.log('*******满足条件  输出', prev, '*********');
      res.push(generateBoard(prev))
      return
    }

    // 尝试摆第index行的皇后 尝试[0, n-1]列
    for (let columnIndex = 0; columnIndex < n; columnIndex++) {
      console.log(tag(rowIndex, '/', true) + `第${columnIndex}列` + tag(rowIndex, '/', false))
      // 在列上不冲突
      let columnNotConflict = !columns[columnIndex]
      // 在对角线1上不冲突
      let dia1NotConflict = !dia1[rowIndex + columnIndex]
      // 在对角线2上不冲突
      let dia2NotConflict = !dia2[rowIndex - columnIndex]

      if (columnNotConflict && dia1NotConflict && dia2NotConflict) {
        // 都不冲突的话，先记录当前已选位置，进入下一轮递归
        console.log('      △暂时符合，标记对应信息，进入下个值的尝试' + columnIndex);
        record(rowIndex, columnIndex, true)
        putQueen(rowIndex + 1, prev.concat(columnIndex))
        // 递归出栈后，在状态中清除这个位置的记录，下一轮循环应该是一个全新的开始。
        console.log('      ○准备回收columnIndex为' + columnIndex)
        record(rowIndex, columnIndex, false)
      } else {
        console.log('      当columnIndex为' + columnIndex + '不符合');
      }
    }
  }

  putQueen(0, [])

  return res
}

// 生成二维数组的辅助函数
function generateBoard(row) {
  let n = row.length
  let res = []
  for (let y = 0; y < n; y++) {
    let cur = ""
    for (let x = 0; x < n; x++) {
      if (x === row[y]) {
        cur += "Q"
      } else {
        cur += "."
      }
    }
    res.push(cur)
  }
  return res
}
solveNQueens(4)

function tag(num, flag, l) {
  const space = Array.from((new Array(num * 2)), () => '=').reduce((r) => `${r} `, '');
  const equal = Array.from((new Array((5 - num) * 2)), () => '=').reduce((r) => `${r}${flag}`, '');
  if (l) {
    return `${space}${equal}`;
  } else {
    return `${equal}${space}`;
  }
}

var trap = function (height) {
  let ans = 0;
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  while (left < right) {
    console.log('left:', left, 'right:', right, 'leftMax: ', leftMax, 'rightMax: ', rightMax);
    leftMax = Math.max(leftMax, height[left]);
    rightMax = Math.max(rightMax, height[right]);
    console.log('leftMax: ', leftMax, 'rightMax: ', rightMax);
    if (height[left] < height[right]) {
      ans += leftMax - height[left];
      ++left;
    } else {
      ans += rightMax - height[right];
      --right;
    }
    console.log('ans:', ans)
    console.log('=========\n\n\n')
  }
  return ans;
};

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
